import java.util.Arrays;
import java.util.Comparator;

/**
 * 973. 最接近原点的 K 个点
 * https://leetcode-cn.com/problems/k-closest-points-to-origin/
 */
public class Solutions_973 {
    public static void main(String[] args) {
        int[][] points = {{1, 3}, {-2, 2}};
        int K = 1;  // output: {{-2, 2}}

//        int[][] points = {{3, 3}, {5, -1}, {-2, 4}};
//        int K = 2;  // output: {{3, 3}, {-2, 4}}

        int[][] result = kClosest(points, K);
        System.out.println(Arrays.deepToString(result));
    }

    /**
     * 解法二：对一维数组排序（10ms）
     */
    public static int[][] kClosest(int[][] points, int K) {
        int len = points.length;
        // 将 points 中的点到原点的欧几里德距离的结果，添加到一维数组中
        int[] distanceArr = new int[len];
        for (int i = 0; i < len; i++) {
            distanceArr[i] = calcDist(points[i]);
        }
        // 对一维数组进行排序
        Arrays.sort(distanceArr);
        // 最近的 K 个点的中，最大的距离为 j，即小于等于 j 的，就是最近的 K 个点之一
        int j = distanceArr[K - 1];
        int[][] res = new int[K][];
        int idx = 0;
        for (int i = 0; i < len; i++) {
            if (K < 1) {
                // 最近的 K 个点已经找到
                break;
            }
            if (calcDist(points[i]) <= j) {
                // points[i] 坐标，是最近的 K 个点之一
                res[idx++] = points[i];
            }
        }
        return res;
    }

    /**
     * 根据一维数组，计算出 [point[0], point[1]] 到 [0, 0] 的欧几里得距离
     * @param point
     * @return
     */
    public static int calcDist(int[] point) {
        return point[0] * point[0] + point[1] * point[1];
    }

    /**
     * 解法一：对二维数组排序（31ms）
     * 勾股定理，第三条边 = 第一条边的平方 + 第二条边的平方
     */
    public static int[][] kClosest2(int[][] points, int K) {
        // 排序：按照欧几里德距离，进行升序排列
        Arrays.sort(points, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                int distance1 = o1[0] * o1[0] + o1[1] * o1[1];
                int distance2 = o2[0] * o2[0] + o2[1] * o2[1];
                return distance1 - distance2;
            }
        });
        // 取排序后数组的前 K 个
        int[][] res = Arrays.copyOf(points, K);
        return res;
    }
}
